package com.markus.code.exam.alibaba;

import org.omg.CORBA.StringHolder;
import sun.plugin2.ipc.windows.WindowsIPCFactory;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/1 19:07
 * todo:
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            String s = scanner.next();
            String t = scanner.next();
            Main demo = new Main();
            System.out.println(demo.process(s,t,n,m));
        }
    }
    private int process(String s, String t,int n,int m){
        if (s == null || n==0 || t == null || m == 0){
            return 0;
        }
        //1.得出s串子串的集合
        int length = ziChuan(s, t);
        //2.遍历这个子串集合，判断是否是t字符串的子序列
        //3.返回这个变量
        return length;
    }
    private int ziChuan(String s,String t){
        int count = 0;
        for (int i=0;i<s.length();i++){
            for (int j=i;j<s.length();j++){
                String son = s.substring(i,j+1);
                int length = lcsLengthPushSpace(son, t);
                if (length == son.length()){
                    count ++;
                }
            }
        }
        return count;
    }
    private int lcsLength(String s1,String s2){
        if (s1 == null || s1.length() == 0 || s2 == null || s1.length() == 0){
            return 0;
        }
        char[] str1 = s1.toCharArray();
        //原字符串的倒置
        char[] str2 = s2.toCharArray();
        //声明dp数组，dp[i][j]为两个字符串比较到str1[i],str2[j]的相同子序列的最大长度
        int dp[][] = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str2.length; i++) {
            dp[0][i] = str2[i] == str1[0] ? 1 : dp[0][i-1];
        }
        for (int i = 1; i < str1.length; i++) {
            dp[i][0] = str2[0] == str1[i] ? 1 : dp[i-1][0];
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]),dp[i-1][j]);
                if (str1[i] == str2[j]){
                    dp[i][j] = Math.max(dp[i-1][j-1]+1,dp[i][j]);
                }
            }
        }
        return dp[str1.length-1][str2.length-1];
    }
    public int lcsLengthPushSpace(String s1,String s2){
        if (s1 == null || s1.length() == 0 || s2 == null || s1.length() == 0){
            return 0;
        }
        char []str1 = s1.toCharArray();
        char []str2 = s2.toCharArray();
        int dp[] = new int[str2.length];
        dp[0] = str1[0]==str2[0] ? 1:0;
        for (int i = 1; i < dp.length ; i++){
            dp[i] = str1[0] == str2[i] ? 1 : dp[i-1];
        }
        for (int i=1;i<str1.length;i++){
            int temp = dp[0];
            dp[0] = str1[i] == str2[0] ? 1 : dp[0];
            for (int j=1;j<dp.length;j++){
                int leftUp = temp;
                temp = dp[j];
                dp[j] = Math.max(dp[j],dp[j-1]);
                if (str1[i] == str2[j]){
                    dp[j] = Math.max(dp[j],leftUp+1);
                }
            }
        }
        return dp[str2.length-1];
    }
}
